//
//  main.cpp
//  43.字符串相乘
//
//  Created by Yan Zihao on 2024/10/1.
//
#include<iostream>
#include<string>
using namespace std;


/*class Solution
{
public:
    string multiply(string num1, string num2)
    {
        string num;
        int a = 0,b = 0,x = 0,y = 0,carry = 0;
        char ch = '0';
        if(num1.size() < num2.size())
        {
            swap(num1,num2);
        }
        a = num1.size() - 1;
        b = num2.size() - 1;
        while(num2[b] != num2[0])
        {
            x = num1[a] - '0';
            y = num2[b] - '0';
            if((x*y) % 10 + carry >= 10)
            {
                ch = ((x*y) % 10 + carry -10) + '0';
                carry = (x*y)/10;
                carry++;
            }
            if((x*y) % 10 + carry < 10)
            {
                ch = ((x*y) % 10 + carry) + '0';
                carry = (x*y)/10;
            }
            num.push_back(ch);
            a--;
            b--;
        }
        reverse(num.begin(),num.end());
        return num;
    }
};*/

class Solution
{
public:
    string multiply(string num1, string num2)
    {
        if (num1 == "0" || num2 == "0") return "0"; // 乘数中有 0 时，直接返回 "0"
        
        int m = num1.size(), n = num2.size();
        vector<int> result(m + n, 0);  // 初始化结果数组
        
        // 从个位开始逐位相乘
        for (int i = m - 1; i >= 0; --i)
        {
            for (int j = n - 1; j >= 0; --j)
            {
                int mul = (num1[i] - '0') * (num2[j] - '0');  // 当前位乘积
                int sum = mul + result[i + j + 1];  // 当前位置累加上已有的结果
                
                result[i + j + 1] = sum % 10;  // 保存个位部分
                result[i + j] += sum / 10;  // 进位到前一位
            }
        }
        
        // 将结果转换为字符串，去掉前导零
        string resultStr;
        for (int num : result)
        {
            if (!(resultStr.empty() && num == 0))
            {  // 跳过前导零
                resultStr.push_back(num + '0');
            }
        }
        
        return resultStr.empty() ? "0" : resultStr;
    }
};
